/**************************************************************************
*   Copyright (C) 2010 Chernov Dmitry                                     *
*                                                                         *
*   This program is free software; you can redistribute it and/or modify  *
*   it under the terms of the GNU General Public License as published by  *
*   the Free Software Foundation; either version 2 of the License, or     *
*   (at your option) any later version.                                   *
*                                                                         *
*   This program is distributed in the hope that it will be useful,       *
*   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
*   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
*   GNU General Public License for more details.                          *
*                                                                         *
*   You should have received a copy of the GNU General Public License     *
*   along with this program; if not, write to the                         *
*   Free Software Foundation, Inc.,                                       *
*   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
***************************************************************************/

#include "MarbleTask.h"
#include "MarbleGameSolver.h"

#include <iostream>
#include <sstream>
#include <memory.h>


MarbleTask::MarbleTask( const std::string& field,
                        MarbleGameSolver* manager ) :   m_initialized(false),
                                                        m_size(0),
                                                        m_sizeTotal(0),
                                                        m_maxDepth(MAX_DEPTH_DEFAULT),
                                                        m_depth(0),
                                                        m_positioned(0),
                                                        m_dir(none)
{
    m_manager = manager;
    loadFromString(field);
}

MarbleTask::MarbleTask() : m_initialized(false)
{}

MarbleTask::~MarbleTask()
{}

void MarbleTask::loadFromString( const std::string& field )
{
    std::istringstream inpStream(field);
    if( ! ( inpStream >> m_size >> m_noMarbles >> m_noWalls ) )
    {
        std::cout << "problem reading field parameters" << std::endl;
        return;
    }

    m_sizeTotal = m_size*m_size;

    if( !( m_noMarbles <= m_sizeTotal ) )
    {
        std::cout << "number of marbles can't be greater than total field size" << std::endl;
        return;
    }

    int x = 0, y = 0;

    // Get all the marble coordinates
    for( int i = 1; i <= m_noMarbles; i++ )
    {
        if( !( inpStream >> y >> x ) )
        {
            std::cout << "error parsing marble coordinates" << std::endl;
            return;
        }

        if( ( (x >= 0) && (x < m_size) ) &&
            ( (y >= 0) && (y < m_size) ) )
        {
            Marble mar( i,  pointToIndex( x, y ) );
            m_marbles.push_back(mar);
        }
        else
        {
            std::cout << "wrong input data : marble position out of range " << x << " "<< y  << std::endl;
            return;
        }
    }

    int n_holes = 0;

    // Now get all the hole coordinates
    for( int i = 1; i <= m_noMarbles; i++ )
    {
        if( !( inpStream >> y >> x ) )
        {
            std::cout << "error parsing marble coordinates" << std::endl;
            return;
        }

        if( ( (x >= 0) && (x < m_size) ) &&
            ( (y >= 0) && (y < m_size) ) )
        {
            Hole hole( i, pointToIndex( x, y ) );
            m_holes.insert( std::make_pair<int, Hole>( pointToIndex( x, y ), hole ) );
            n_holes++;
        }
        else
        {
            std::cout << "wrong input data : hole position out of range " << x << " "<< y << std::endl;
            return;
        }
    }

    if( n_holes !=  m_noMarbles )
    {
        std::cout << "number of holes not correspond number of marbles";
        return;
    }

    int x2 = 0, y2 = 0;

    std::map< int, Wall >::iterator it_walls;

    // After all get all the wall coordinates
    for( int i = 0; i < m_noWalls; i++ )
    {
        if( !( inpStream >> y >> x >> y2 >> x2 ) )
        {
            std::cout << "error parsing wall coordinates" << std::endl;
            return;
        }

        int index1 = pointToIndex( x, y );
        int index2 = pointToIndex( x2, y2 );

        Wall::wallType wt1;
        Wall::wallType wt2;

        if( (x == x2) && (y != y2) )
        {
            if( y > y2 )
            {
                wt1 = Wall::wall_top;
                wt2 = Wall::wall_bottom;
            }
            else
            {
                wt1 = Wall::wall_bottom;
                wt2 = Wall::wall_top;
            }
        }
        else if( (y == y2) && (x != x2) )
        {
            if( x > x2 )
            {
                wt1 = Wall::wall_left;
                wt2 = Wall::wall_right;
            }
            else
            {
                wt1 = Wall::wall_right;
                wt2 = Wall::wall_left;
            }
        }
        else
        {
            std::cout << "wrong wall informatiion : cells are not bounding" << std::endl;
            return;
        }

        if( ( it_walls = m_walls.find(index1) ) == m_walls.end() )
            m_walls.insert( std::make_pair<int, Wall>( index1, Wall( index1, wt1 ) ) );
        else
            it_walls->second.addWall(wt1);
        if( ( it_walls = m_walls.find(index2) ) == m_walls.end() )
            m_walls.insert( std::make_pair<int, Wall>( index2, Wall( index2, wt2 ) ) );
        else
            it_walls->second.addWall(wt2);
    }

    m_initialized = true;
}

bool MarbleTask::isPassEnabled( int ind, direction dir )
{
    // Check collisions with other marbles
    int marbleNo = 0;
    if( ( marbleNo = getMarbleAtPos(ind) ) != -1 )
    {
        if( !m_marbles[marbleNo].positioned() )
            return false;
    }

    // Check collisions with walls
    std::map<int, Wall>::iterator it_walls;
    if( ( it_walls = m_walls.find(ind) ) != m_walls.end() )
    {
        Wall& wall = it_walls->second;

        if( ( dir == up ) && wall.is( Wall::wall_bottom ) )
            return false;
        if( ( dir == down ) && wall.is( Wall::wall_top ) )
            return false;
        if( ( dir == right ) && wall.is( Wall::wall_left ) )
            return false;
        if( ( dir == left ) && wall.is( Wall::wall_right ) )
            return false;
    }

    return true;
}

MarbleTask::moveStatus MarbleTask::move( int turn, int marbleNo, int src_ind, int dst_ind )
{
    if( src_ind == dst_ind )
        return not_moved;

    Marble& mar = m_marbles[marbleNo];
    mar.move( dst_ind, turn );

    std::map<int, Hole>::iterator it_holes;
    if( ( it_holes = m_holes.find(dst_ind) ) != m_holes.end() )
    {
        Hole& hole = it_holes->second;

        if( hole.matches( mar.getId() ) )
        {
            mar.setPositioned(turn);
            return commit;
        }
        else
        {
            if( getMarbleAtPos(dst_ind) == -1 )
                return failure;
        }
    }

    return regular;
}

void MarbleTask::solve()
{
    if( !m_initialized )
    {
        std::cout << "game wasn't properly initialized" << std::endl;
        return;
    }

    if( m_manager == NULL )
    {
        std::cout << "needs an instance of manager to work" << std::endl;
        return;
    }

    if( m_dir != none )
        m_doneRolls.push_back( m_dir );

    innerFind( m_depth, m_dir, m_positioned );
}

void MarbleTask::innerFind( int depth, direction dir, int current_positioned )
{
    if( depth++ > m_maxDepth )
        return;

    if( depth > m_manager->yetShortestSol() )
    {
        // Won't find anything better iff going further
        return;
    }

    //showField();

    int done = 0;
    if( dir != none )
    {
        if( !rollBoard( depth, done, dir ) )
            return;

        if( current_positioned + done == m_noMarbles )
        {
            // Solution found, now store it in common place
            unrollBoard(depth);
            m_manager->saveSolution( m_doneRolls );
            return;
        }
    }

    bool subtaskingRational = ( m_maxDepth - depth > MIN_SUBTASK_DEPTH );   // To avoid to small tasks
    int i = (dir + 1)%5;

    for( ; i != dir; i = ( ++i )%5 )
    {
        if( i == none )
            continue;

        if( subtaskingRational )
        {
            if( m_manager->freeThreadsPresent() )
            {
                // Give subtask to another thread in multithread solver
                // if the subtask is big enough
                m_dir = direction(i);
                m_depth = depth;
                m_positioned = current_positioned + done;
                m_manager->addMarbleTask(this);
                continue;
            }
        }

        m_doneRolls.push_back( direction(i) );
        innerFind( depth, direction(i), current_positioned + done );
        m_doneRolls.pop_back();
    }

    unrollBoard(depth);
}

bool MarbleTask::rollBoard( int turn, int& done, direction dir )
{
    done = 0;
    int nMoved = 0;

    int index = 0;

    if( ( dir == down ) || ( dir == right ) )
        index = m_sizeTotal - 1;

    int marbleNo = 0;

    std::vector<int> rolled;
    rolled.reserve(m_noMarbles);

    do
    {
        if( ( marbleNo = getMarbleAtPos(index) ) != -1 )
        {
            if( m_marbles[marbleNo].positioned() )
                continue;

            moveStatus res = roll( turn, marbleNo, index, dir );

            if( res == commit )
                done++;
            else if( res == failure )
            {
                m_marbles[marbleNo].unmove(turn);

                size_t sz = rolled.size();

                for( size_t i = 0; i < sz; ++i )
                    m_marbles[ rolled[i] ].unmove(turn);

                return false;
            }

            if( res != not_moved )
            {
                nMoved++;
                rolled.push_back( marbleNo );
            }
        }
    } while( ( index = getNextCellIndex( index, dir ) ) != -1 );

    if( nMoved == 0 )
        return false;

    return true;
}

void MarbleTask::unrollBoard( int turn )
{
    int size = m_marbles.size();

    for( int i = 0; i < size; ++i )
    {
        m_marbles[i].unmove(turn);
    }
}

MarbleTask::moveStatus MarbleTask::roll( int turn, int marbleNo, int index, direction dir )
{
    int dst_ind = index;
    int dst_ind_prev = dst_ind;

    for( int i = 0; i < m_size; i++ )
    {
        if( dir == up )
        {
            if( dst_ind - m_size >= 0 )
                dst_ind -= m_size;
            else
                break;
        }
        else if( dir == right )
        {
            if( ( ( dst_ind + 1 )/m_size == index/m_size ) &&
                ( ( dst_ind + 1 ) < m_sizeTotal ) )
                ++dst_ind;
            else
                break;
        }
        else if( dir == down )
        {
            if( dst_ind + m_size < m_sizeTotal )
                dst_ind += m_size;
            else
                break;
        }
        else if( dir == left )
        {
            if( ( ( dst_ind - 1 )/m_size == index/m_size ) &&
                ( ( dst_ind - 1 ) >= 0 ) )
                --dst_ind;
            else
                break;
        }

        if( !isPassEnabled( dst_ind, dir ) )
        {
            dst_ind = dst_ind_prev;
            break;
        }

        if( isHolePresent( dst_ind ) )
            break;

        dst_ind_prev = dst_ind;
    }

    return move( turn, marbleNo, index, dst_ind );
}

int MarbleTask::getNextCellIndex( int index, direction dir )
{
    if( dir == down )
    {
        int res = --index;
        return ( res >= 0 )? res : - 1;
    }
    else if( dir == left )
    {
        int x = index%m_size;
        int y = index/m_size;

        if( y + 1 < m_size )
            y++;
        else
        {
            if( x + 1 < m_size )
            {
                x++;
                y = 0;
            }
            else
                return -1;
        }

        return pointToIndex(x, y);
    }
    else if( dir == up )
    {
        int res = ++index;
        return ( res < m_sizeTotal )? res : - 1;
    }
    else if( dir == right )
    {
        int x = index%m_size;
        int y = index/m_size;

        if( y - 1 >= 0 )
            y--;
        else
        {
            if( x - 1 >= 0 )
            {
                x--;
                y = m_size - 1;
            }
            else
                return -1;
        }
        return pointToIndex(x, y);
    }

    return -1;
}

void MarbleTask::showField()
{
    int marbleNo = 0;

    for( int i = 0; i < m_sizeTotal; i++ )
    {
        if( i%m_size == 0 )
            std::cout << std::endl;

        std::cout << " ";

        if( ( marbleNo = getMarbleAtPos(i) ) != -1 )
        {
            std::cout << m_marbles[marbleNo].getId();
            continue;
        }

        if( isHolePresent(i) )
        {
            std::cout << 'o';
            continue;
        }

        std::cout << " ";
    }

    std::cout << std::endl;
    std::cin.get();
}

bool MarbleTask::isHolePresent( int pos )
{
    std::map<int, Hole>::iterator it_holes;
    if( ( it_holes = m_holes.find( pos ) ) != m_holes.end() )
        return true;

    return false;
}

int MarbleTask::getMarbleAtPos( int pos )
{
    int size = m_marbles.size();
    for( int i = 0; i < size; ++i )
    {
        if( m_marbles[i].getPosition() == pos )
        {
            if( !m_marbles[i].positioned() )
                return i;
        }
    }

    return -1;
}
